'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-06-28 14:04:42
'''
'''
5450. 满足条件的子序列数目
给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
'''
from typing import List
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        re = 0
        nums.sort()
        
        i = 0
        j = len(nums)-1
        while i<=j:
            if nums[i]+nums[j]<=target:
                re += 2**(j-i)
                i += 1
            else:
                j -= 1
        return re%1000000007


if __name__ == "__main__":
    solution = Solution()
    nums = [3,5,6,7]
    target = 9
    print(solution.numSubseq(nums, target))